The present invention relates generally to a variable length coding and/or decoding system used for compression coding and/or decoding moving picture signals or the like. More specifically, the invention relates to a variable length coding and/or decoding system capable of decoding both in forward and backward directions, and a recording medium for recording data or programs for use in the system.
A variable length code is a code system of a short code length on average, which is obtained by assigning a short code length of codes to a frequently appearing symbol and a long code length of codes to a rarely appearing symbol. Therefore, if a variable length code is used, the amount of data can be considerably compressed in comparison with the amount of data before being coded. As a method for forming such a variable length code, the Huffman algorithm suitable for memoryless sources is known.
In general, there is a problem in that, if an error is mixed in a variable length code due to a channel error of coded data or the like, a decoding system can not correctly decode the data due to the propagation of influence of the error after the error is mixed therein. In order to avoid this problem, there is a typical method for inserting synchronization patterns at intervals to prevent the propagation of an error when there is a possibility that the error may occur in a channel. Bit patterns, which do not appear by any combinations of variable length codes, are assigned to the synchronization patterns. According to this method, even if coded data can not be decoded due to an error occurring therein, it is possible to prevent the propagation of the error to correctly decode the coded data by finding the next synchronization pattern.
However, even if the synchronization patterns are used, the coded data can not be decoded until the next synchronization pattern is found from the position, at which the coded data can not be correctly decoded due to the error occurring therein as shown in FIG. 1A.
Therefore, there is known a method for changing the variable length codes from the usual configurations shown in FIGS. 2A through 2C to the configurations shown in FIGS. 3A through 3C to form code words, which can be decoded in a usual forward direction as well as in a backward direction as shown in FIG. 1B. Since the coded data of such code words are also readable in the backward direction, the code words can be also used for reverse reproduction in a storage medium, such as a disc memory, for storing the coded data. This variable length code, which can be decoded in the forward direction as well as in the backward direction, will be hereinafter referred to as a xe2x80x9creversible codexe2x80x9d.
An example of the reversible code is disclosed in Japanese Patent Laid-Open No. 5-300027, entitled xe2x80x9cReversible Variable Length Coding Systemxe2x80x9d. This publicly-known reversible code is a variable length code, which can also be decoded in the backward direction by adding bits to the ends of code words of a Huffman code, which is a variable code capable of being decoded in the forward direction as shown in FIGS. 2A through 2C, so that the respective code words are not coincident with other code words having longer code lengths as shown in FIGS. 3A through 3C. However, this reversible code contains many useless bits to have a long average code length since the bits are added to the ends of the code words of the variable length code, which can be decoded only in the forward direction. Consequently, the coding efficiency is considerably deteriorated in comparison with the variable length code, which can be decoded only in the forward direction.
There is also a problem in that the conventional reversible code can not be decoded in the backward direction if synchronization intervals are set every predetermined interval. For example, ITU-T H.263 (1996) can align synchronization patterns every 8 bits (=1 byte), i.e., it can set positions, at which the synchronization patterns can be inserted, every 1 byte. In order to realize such alignment of synchronization intervals, stuffing codes shown in FIG. 34 are inserted before the synchronization patterns. In such a case, in the conventional reversible codes, there is a problem in that the backward decoding can not be carried out due to the stuffing bits.
Moreover, when the reversible code is simply decoded, there is a problem in that the circuit scale and the amount of operation have to be twice as large as those in a usual decoding system for variable length codes, which can be decoded only in the forward direction, by the amount decoded in the backward direction.
There is another problem in that the conventional reversible code can not be decoded in the backward direction by syntax of input information as the case may be. For example, in the case of source symbols having syntax shown in FIG. 5A, the sign of symbol B is determined by symbol A. Coded data obtained by coding source symbols having such syntax can not be decoded in the backward direction since the symbol B can not be decoded unless the symbol A has been decoded as shown in FIG. 5B.
As a coding system used when the number of source symbols is high, there is a system using escape codes. This system using escape codes has code words corresponding to a small number of source symbols having a high appearance frequency as a code-word table, and encodes a large majority of source symbols having a low appearance frequency by the combinations of escape codes and fixed length codes. Also in this system using escape codes, there has been provided a system for applying escape codes to the prefix and suffix of a variable length code, similar to the variable length code capable of being decoded both in the forward and backward directions.
In the conventional coding and/or decoding system using escape codes, it is required to search the code-word table for the presence of code words in order to distinguish the code words existing in the code-word table from the code words to be coded using escape codes.
That is, as described above, since the conventional reversible code, i.e., the variable length code capable of being decoded both in the forward and backward directions, is formed by adding bits to the suffix of code words of a variable length code capable of being decoded only in the forward direction, there is a problem in that useless bit patterns are increased to increase an average code length, so that the coding efficiency is considerably deteriorated in comparison with the variable length code capable of being decoded only in the forward direction. In addition, if the synchronization intervals are set every predetermined intervals using stuffing bits, there is a problem in that the reversible code can not be decoded in the backward direction due to the stuffing bits. Moreover, if the reversible code is simply decoded, there is a problem in that the circuit scale and the amount of operation have to be twice as large as those in a usual decoding system for variable length codes capable of being decoded only in the forward direction, by the amount decoded in the backward direction, and there is a problem in that it is not possible to decode in the backward direction by the syntax of input information as the case may be.
It is therefore an object of the present invention to provide a moving picture decoding system which can restrain the quality of a decoded image from greatly deteriorating even if an error occurs in any portion of a code, and which can efficiently decode the code even if only a part of the code can be decoded due to the error.
According to a first aspect of the present invention, a moving picture decoding system comprises: input means for inputting a first code string arranging in order from the prefix to the suffix, and a second code string arranging in order from the suffix to the prefix in the backward direction: and decoding means for decoding the first code string in order from the prefix to the suffix and for decoding the second code string in order from suffix to prefix in the backward direction. In this system, the first code string arranging in the forward direction from the prefix to the suffix and the second row arranging in the backward direction from the suffix to the prefix are decoded. Therefore, even if an error occurs in one of the rows, the decoding can be carried out without influencing the other row.
According to a second aspect of the present invention, a moving picture decoding system comprises: input means for inputting code string which have been divided into a plurality of regions with respect to each of frames; decoding means for decoding the code string of each of the regions supplied from the input means; and rearranging means for rearranging the data of each of the regions supplied from the decoding means, in correct order. In this system, the code string wherein the regions is arranged in order of importance of the rearranged image. Therefore, even if an error occurs in a part of data, the region which has been able to be decoded is an important portion, so that it is possible to restrain the lack of the important portion of the image in comparison with the conventional system.
According to a third aspect of the present invention, the moving picture decoding system as set forth includes detection means for detecting an error with respect to the first and second code string and the coded data/signal, respectively, wherein the decoding is carried out using only the data wherein no error has been detected by the error detection means. In this system, the detection of error is carried out when the divided code string is decoded. Therefore, it is possible to form a reproduced image by means of only the correctly decoded data. It is also possible to predict and complement the data which has not been able to be decoded, by means of the correctly decoded data.
According to a fourth aspect of the present invention, the moving picture decoding system includes error detecting means for detecting an error with respect to the code string and the decoded data/signal; and predicting means for predicting the region which as not been able to be decoded, on the basis of the decoded region when an error is detected by means of the error detecting means. In this system, the regions of a higher probability of decoding in both of the code string divided into two parts, can complement the regions of a lower probability of decoding in both of the code string divided into two parts. Therefore, it is possible to predict and complement the data of the data lacking region.
According to a fifth aspect of the present invention, the moving picture decoding system as set forth in the fourth aspect includes means for rearranging and decoding regions in accordance with the region rearranging data included in the code string. In this system, the code string that the coding order has been changed in accordance with the image is decoded. Therefore, even if the data have not been able to be fully decoded due to errors, it is possible to increase the probability of decoding with respect to the important portion of the coding data.
It is another object of the present invention to provide a practical variable-length decoding system which can be decoded in either of the forward and backward directions.
Specifically, it is an object of the present invention to provide a variable-length decoding system which can be decoded in either of the forward and backward directions and wherein the number of useless bit patterns is small and the coding efficiency is high.
It is a further object of the present invention to provide a variable-length decoding system which can be decoded in either of the forward and backward directions and which is unnecessary for a great memory capacity even if the number of source symbols is great.
In order to accomplish the aforementioned and other objects, according to a sixth aspect of the present invention, a variable-length coding system which assigns code words to a plurality of source symbols, the code words having a code length in accordance with the probability of the source symbols, and which outputs as coding data, the code words corresponding to the inputted source symbols, comprises: a code-word table for storing a plurality of code words so as to correspond to the source symbols, the code words being configured so as to be able to determine the pause between codes by the weights of the code words; and coding means for selecting a code word corresponding to the inputted source symbol from the code-word table and for outputting the selected code word as coding data.
The term xe2x80x9cweight of code wordxe2x80x9d corresponds to a hamming distance from the minimum or maximum value of the code word. When the code word is a binary code, the minimum value of the code word is xe2x80x9c0xe2x80x9d in all cases and the maximum value of the code word is xe2x80x9c1xe2x80x9d in all cases, so that the weight of the code word corresponds to the number of xe2x80x9c 1xe2x80x9d or xe2x80x9c0xe2x80x9d. The position wherein the weight of the code word is a predetermined value indicates the pause between codes in the variable-length code.
With respect to the plurality of code words stored in the code-word table, a fixed-length code, i.e. a constant length of code, is unnecessary to be added to at least one of the prefix and suffix thereof.
In addition, unlike a code wherein bits are added to the suffix of a variable-length code decodable in only the forward direction such as reversible code disclosed in the aforementioned Japanese Patent Laid-Open, a reversible code is originally configured without the addition of excessive bits, so that it is possible to obtain a variable-length code wherein the number of useless bit patterns is small and wherein the coding efficiency is great.
Moreover, a variable-length code can be obtained in accordance with the probability of appearance of source symbols by selecting a plurality of code configuring methods and a code of the minimum average code-length from parameters, on the basis of the probability of source symbols.
According to a seventh aspect of the present invention, a variable-length decoding system which can decode in either of the forward and backward directions and which decodes a variable-length code to which synchronizing codes are inserted at regular intervals, comprises: a forward decoding means for decoding a variable-length code in the forward direction and for detecting an error of a code word of the variable-length code; a backward decoding means for decoding the variable-length code in the backward direction and for detecting an error of a code word of the variable-length code; and decoded-value deciding means for deciding a decoded value on the basis of the decoded results by the forward decoding means and the backward decoding means, wherein the decoded value at the position in which the error is detected in accordance with the results of detection of the error by the forward decoding means and the backward decoding means.
Specifically, in the decoded-value deciding means, (a) when errors have been detected by both of the forward decoding means and the backward decoding means and when the detected positions of the errors have not passed each other, only the decoded result wherein no error has not been detected, is used as the decoded value, (b) when errors have been detected by both of the forward decoding means and backward decoding means and when the detected positions of the errors have not passed each other, the decoded result wherein no error has not been detected by both of the forward decoding means and the backward decoding means, is used as the decoded value, (c) when an error has been detected by one of the forward decoding means and the backward decoding means, the decoded value with respect to the code word at the position wherein the error has been detected is abandoned, and the decoded result in the backward direction is used as the decoded value with respect to the subsequent code word, and (d) when errors have been detected with respect to the same code word by means of the forward decoding means and the backward decoding means, the decoded value with respect to the code word at the position wherein an error has been detected is abandoned, and the decoded result in the backward direction is used as the decoded value with respect to the subsequent code word.
In this variable length decoding system, when the decoded value is decided on the basis of the decoded results by the forward decoding means and the backward decoding means which use a function for detecting errors in code words of a variable-length code, it is possible to effectively decode the reversible code outputted from the aforementioned variable-length coding system, against the errors such as channel errors, by deciding the decoded value at the position wherein the errors have been detected in accordance with the detected results of errors by the forward decoding means and the backward decoding means and the backward decoding means.
According to an eighth aspect of the present invention, a variable-length decoding system which can be adapted to the variable-length coding system according to the present invention and which decodes coding data of variable-length codes decodable in either of the forward and backward directions, comprises: forward decoding means for decoding a variable-length code in the forward direction; backward decoding means for decoding a variable-length code in the backward directions; and fixed-length code decoding means for decoding a fixed-length code, wherein when specific codes (escape codes) representative of the prefix and suffix of the fixed-length code have been decoded when the variable-length code is decoded by the forward decoding means and the backward decoding means, the subsequent coding data is decoded by the fixed-length code decoding means.
According to a ninth aspect of the present invention, there is provided a variable-length decoding system which decodes coding data of a variable-length code decodable in either of the forward and backward directions. In this system, the code-length of a variable-length code is derived on the basis of the number of a predetermined xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d of the code word, and the value determined by a Pascal""s triangle is assigned to the value of a joint. Then, the rank order values of different code words of the same code-length is derived by means of a directed graph wherein the arrows from each joint to the next joint correspond to xe2x80x9c1xe2x80x9d and xe2x80x9c0xe2x80x9d of the code words, and a decoded value is calculated by means of the rank order value and the directed graph.
In this variable-length decoding system, it is possible to determine the pause between the codes by the number of the weights of the code words, i.e. the code length, similar to the variable-length coding system according to the present invention. In addition, this system uses variable-length code words configured by code words decodable in either of the forward and backward directions, the value determined by a Pascal""s triangle is assigned to the value of a joint, and the decoded value is calculated by the directed graph (decoding graph) wherein the arrows from each joint to the next joint corresponds to xe2x80x9c1 xe2x80x9d and xe2x80x9c0xe2x80x9d of the code words. Therefore, it is possible to decode the variable-length code by a small memory capacity even if the number of source symbol is great.
According to a tenth aspect of the present invention, a variable-length decoding system which can be adapted to the variable-length coding system according to the present invention and wherein a moving picture decoder decodes coding data decoded into a variable-length code which can decode an orthogonal transform coefficient produced by the orthogonal transform every blocks by means of a moving picture encoder, in either of the forward and backward directions, comprises: forward decoding means for decoding a variable-length code in the forward direction; and backward decoding means for decoding a variable-length code in the backward direction, wherein when the forward decoding means decodes the variable-length code, the last of the block is determined on the basis of the appearance of a code word representative of the orthogonal transform coefficient of the last of the block, and when the backward decoding means decodes the variable-length code, the head of the block is determined by the code word representative of the last orthogonal coefficient of the last block.
In the variable-length decoding system according to the present invention, the first code-word table corresponding to the orthogonal transform coefficient other than the last of the block is configured with respect to each of the plurality of coding modes. However, the second code-word table corresponding to the orthogonal transform coefficient of the last of the block is used for the respective coding modes in common, so that it is possible to cope with the change of the code-word tables by the coding mode, and to find the pause between blocks by the appearance of the code word representative of the last orthogonal transform coefficient of the last block, so that the decoding can be syntactically in either direction.